package hanjia;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/11-下午10:49
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode236 {
    //自己想的
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        int max = 0;
        TreeNode result = null;
        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;

            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (findDept(poll, p) != -1 && findDept(poll, q) != -1) {
                    if (count > max) {
                        max = count;
                        result = poll;
                    }
                }


                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }


            }


        }
        return result;


    }

    public int findDept(TreeNode root, TreeNode target) {
        if (root == null) {
            return -1;
        }

        if (root == target) {
            return 1;
        }
        int left = -1;
        left = findDept(root.left, target);
        if (left != -1) {
            return left + 1;
        }
        int right = -1;
        right = findDept(root.right, target);
        if (right != -1) {
            return right + 1;
        }
        return -1;


    }

    //经过提示
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        if (leftNode != null && rightNode != null) {
            return root;
        }
        if (leftNode == null && rightNode != null) {
            return rightNode;
        }
        if (leftNode != null && rightNode == null) {
            return leftNode;
        }
        return null;


    }


}
